2- جهت تشخيص پيچيدگي زماني از روي شبه كد، كافيست تعداد دفعات تكرار حلقه را پيدا كنيد، اگر سوال چند گزينه اي بود، كافيست موارد كاملا غلط را پيدا و از مقايسه كنار بگذاريد.
-اگر چند حلقه تو در تو داشت، تعداد دفعات تكرار همه حلقه ها را، در هم ضرب كنيد.
- اگر حلقه هاي مجزا داشت تعداد تكرار حلقه ها را با هم جمع كنيد. و آنچه از همه بزركتر بود( از نظر مرتبه) ميتواند تعيين كننده باشد و از بقيه جمله ها صرف نظر كنيد.
سوال 32 فصل 1: الف : n^c , و ب و ج: O(n^c) ,big-o يعني هرگاه عدد يك را داخل پرانتز ديديد، بدانيد كه مقدار پيچيدگي زماني مقدار ثابت سي هست O(1) big-o و متغير c را جايگزين O(1) big-o كنيد.
اين گزاره را براي تعيين پاسخ تست ها در نظر داشته باشيد:
f(n) + g(n) متعلق است به (max(f(n)+g(n)) يعني در جمع چند تابع، هر كدام مرتبه بيشتري داشته باشد تعيين كننده هست و نبايد پيچيدگي آنها را باهم جمع كرد
f^2(n) متعلق است به امگا f(n)
ساير نكات و پاسخ هاي فصل هاي ابتدائي را از همين قسمت دانلود كنيد.
منبع صفحه شخصی استاد D: